package com.lft.tree14.tree234;
// 摘自 Java 数据结构与算法第二版

//234 树

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

public class Tree234Demo {
	public static void main(String[] args) {
		Tree234 tree = new Tree234();
		Random rand = new Random();
		Set<Integer> set = new HashSet<>();// 重复键好像有问题
		for (int i = 0; i < 20; i++) {
			set.add(rand.nextInt(100));
		}
		Iterator<Integer> it = set.iterator();
		while (it.hasNext()) {
			tree.insert(it.next());
		}
		tree.displayTree();
		tree.sort(tree.root);
	}
}

/**
 * 2-3树实现类
 */
class Tree234 {
	public Node root = new Node();
	
	public int find(int key) {
		Node curNode = root;
		int childNum;
		while (true) {
			if ((childNum = curNode.findItem(key)) != -1) {
				return childNum;
			} else if (curNode.isLeaf()) {
				return -1;
			} else {
				curNode = getNextChild(curNode, key);
			}
		}
	}
	
	private Node getNextChild(Node curNode, int key) {
		int nums = curNode.getNumItems();
		for (int i = 0; i < nums; i++) {
			if (key < curNode.getItem(i).data) {
				return curNode.getChild(i);
			}
		}
		return curNode.getChild(nums);
		
	}
	
	public void insert(int data) {
		Node curNode = root;
		DataItem item = new DataItem(data);
		while (true) {
			// 分裂步骤：将第三个数值和相应子节点移到新的节点，新节点作为当前节点的右兄弟节点
			// 将第二个数值插入父节点，调整父节点的子节点，将新节点连到父节点上
			if (curNode.isFull()) {// 满节点进行分裂
				split(curNode);
				curNode = curNode.getParent();
				curNode = getNextChild(curNode, data);// 这 2 步分裂后回退再次找插入位置
			} else if (curNode.isLeaf()) {
				break;
			} else {
				curNode = getNextChild(curNode, data);
			}
		}
		curNode.insertItem(item);
	}
	
	private void split(Node node) {
		DataItem itemB, itemC;// 对应第二、三个数值
		Node parent, child2, child3;// 对应后 2 个子节点
		int itemIndex;
		itemC = node.removeItem();
		itemB = node.removeItem();
		child2 = node.disconnectChild(2);
		child3 = node.disconnectChild(3);
		Node newRight = new Node();// 新的兄弟节点
		if (node == root) {// 根节点满了需要新建根节点
			root = new Node();
			parent = root;
			root.connectChild(0, node);
		} else {
			parent = node.getParent();
		}
		itemIndex = parent.insertItem(itemB);
		int num = parent.getNumItems();
		// 插入 itemB 后，父节点的相应子节点位置也要右移
		for (int j = num - 1; j > itemIndex; j--) {
			Node temp = parent.disconnectChild(j);
			parent.connectChild(j + 1, temp);
		}
		parent.connectChild(itemIndex + 1, newRight);
		newRight.insertItem(itemC);
		newRight.connectChild(0, child2);
		newRight.connectChild(1, child3);
		
	}
	
	public void displayTree() {
		fineDisplay(root, 0, 0);
	}
	
	private void fineDisplay(Node node, int level, int childNum) {
		System.out.println("level=" + level + " child=" + childNum + " ");
		node.displayNode();
		int nums = node.getNumItems();
		for (int i = 0; i < nums + 1; i++) {//child 比数据个数多 1
			Node child = node.getChild(i);
			if (child != null) {
				fineDisplay(child, level + 1, i);
			} else {
				return;
			}
		}
		
	}
	
	// 从小到大遍历
	public void sort(Node node) {
		int nums = node.getNumItems();
		for (int i = 0; i < nums; i++) {
			Node child = node.getChild(i);
			if (child.isLeaf()) {
				child.displayNode();
				System.out.println(node.getItem(i).data);
			} else {
				sort(child);
			}
		}
		Node last = node.getChild(nums);
		if (last.isLeaf()) {
			last.displayNode();
		} else {
			sort(last);
		}
	}
	
}

/**
 * 2-3树节点类
 * 主要是一个包含数值的对象的数组，一个子节点数组
 */
class Node {
	/**
	 * 常量4表示2-3-4树
	 */
	private static final int N = 4;
	/**
	 * 当前节点数据个数
	 */
	private int numItems;
	/**
	 * 当前节点的父节点
	 */
	private Node parent;
	/**
	 * 当前节点的子节点数组
	 * 每个节点可以最多有4个子节点。
	 */
	private Node[] nodeArray = new Node[N];
	/**
	 * 当前节点的数据项数组
	 * 每个节点可以最多有3个数据项。
	 */
	private DataItem[] itemArray = new DataItem[N - 1];
	
	/**
	 * 指定位置连接子节点
	 * @param index 指定位置索引
	 * @param child 子节点
	 */
	public void connectChild(int index, Node child) {
		nodeArray[index] = child;
		if (child != null) {
			child.parent = this;
		}
	}
	
	/**
	 * 解绑指定位置子节点
	 * @param index 要解绑的位置索引
	 * @return 解绑的节点
	 */
	public Node disconnectChild(int index) {
		Node temp = nodeArray[index];
		nodeArray[index] = null;
		return temp;
	}
	
	/**
	 * 获取子节点
	 * @param index
	 * @return
	 */
	public Node getChild(int index) {
		return nodeArray[index];
	}
	
	/**
	 * 获取父节点
	 * @return
	 */
	public Node getParent() {
		return parent;
	}
	
	/**
	 * 获取数据项数量
	 * @return
	 */
	public int getNumItems() {
		return numItems;
	}
	
	/**
	 * 获取数据项
	 * @param index 要获取的索引位置。
	 * @return 数据项
	 */
	public DataItem getItem(int index) {
		return itemArray[index];
	}
	
	/**
	 * 根据 key 在当前节点找索引 index
	 * @param key 要查找的数据项的值
	 * @return 返回索引
	 */
	public int findItem(int key) {
		for (int i = 0; i < numItems; i++) {
			if (itemArray[i] == null) {
				break;
			} else if (itemArray[i].data == key) {
				return i;
			}
		}
		// 找不到返回 - 1
		return -1;
	}
	
	/**
	 * 假设不满时插入，后面通过对满的节点分裂，保证了这一点
	 * @param item 数据项
	 * @return
	 */
	public int insertItem(DataItem item) {
		numItems++;
		int key = item.data;
		for (int i = N - 2; i >= 0; i--) {
			if (itemArray[i] == null) {
				continue;
			} else {
				int curkey = itemArray[i].data;
				if (key < curkey) {
					itemArray[i + 1] = itemArray[i];
				} else {
					itemArray[i + 1] = item;
					return i + 1;
				}
			}
		}
		itemArray[0] = item;
		return 0;
	}
	
	public DataItem removeItem() {
		DataItem temp = itemArray[numItems - 1];
		itemArray[numItems - 1] = null;
		numItems--;
		return temp;
	}
	
	public void displayNode() {
		for (int i = 0; i < numItems; i++) {
			itemArray[i].display();
		}
		System.out.println("/");// 斜线分隔方便显示
	}
	
	public boolean isLeaf() {
		return nodeArray[0] == null;
	}
	
	public boolean isFull() {
		return numItems == N - 1;
	}
}

/**
 * 2-3树数据项
 * 存储一个数值
 */
class DataItem {
	int data;
	
	public DataItem(int data) {
		this.data = data;
	}
	
	public void display() {
		System.out.println("/" + data);
	}
}


